/**
主要回顾：函数的定义方法，条件语句，以及循环语句。
对比选择排序和冒泡排序。
加深理解折半查找（二分查找）
*/

class SortnFind {
    
    /*
    把整型数组转换成字符串并返回。
    */
    public static String toString(int[] arr){
        String result = "";
        for (int i=0; i<arr.length; i++) {
            if (i == 0) {	//开头加上左中括号
                result += "[" + arr[i] + ", ";
            }else if (i == arr.length - 1) {
                result += arr[i] + "]";
            }else {			//结束加上右中括号
                result += arr[i] + ", ";
            }
        }
        return result;
    }
    
    
    /*
    选择排序法
    */
    public static void selectSort(int[] arr){
        //每轮选出该位置的最大值，需要长度减 1 轮（因为前面 N 个排好了，最后一个自然也就好了）
        for (int i=0; i<arr.length-1; i++) {
            //第 1 轮需要从头开始比较，一直比较到最后一个；第 2 轮因为第 1 个已经确定了，从第 2 个开始比较；依此类推。
            for (int j = i+1; j<arr.length; j++) {
                //假定当前元素是最大的，遇到比当前大的就换过来
                if (arr[j] > arr[i]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
    
    /*
    冒泡排序法
    */	
    public static void bubleSort(int[] arr){
        //每轮可以确定一个最小值，需要长度减 1 轮（因为后面 N 个排好了，前面那个自然就是最大值了）
        for (int i=0; i<arr.length-1; i++) {
            //第 1 轮需要重新开始比较，比较 N-1 次；第 2 轮因为最后一个确定了，比较 N-2 次；依此类推。
            for (int j=0; j<arr.length-1-i; j++) {
                //如果当前元素小于后一个，则交换（把小的元素往后挪）
                if (arr[j] < arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
    
    /*
    二分查找法，查找的数组必须有序！限定为从大到小排列。
    若找到，返回该目标所在的位置；否则返回 -1。
    */
    public static int halfSearch(int[] arr, int key){
        int max = 0;				//记录范围最大值的下标
        int min = arr.length-1;		//记录范围最小值的下标
        int mid = (max + min) / 2;	//记录当前比较值的下标
        
        while (arr[mid] != key) {	//如果当前比较值不是查找目标，则继续查找
            if (arr[mid] > key) {	//如果当前值比目标大，说明目标在右边，所以目标最大的可能值是 mid 往右一个
                max = mid + 1;
            }else if (arr[mid] < key) {	//如果当前值比目标小，说明目标在左边，所以目标的最小可能值是 mid 往左一个
                min = mid - 1;
            }
            
            mid = (max + min) / 2;	//重新修改当前比较值
            
            if (max > min) {		//如果可能最大值的下标 > 可能最小值的下标，说明已经找遍了，也没找到。结束查找。
                mid = -1;
                break;
            }
        }
        
        return mid;
    }
    
    public static void main(String[] args) {
        //测试排序方法
        int[] arr = {1, 6, 3, 4, 5};
        System.out.println("Original Array: " + toString(arr));
//		selectSort(arr);	//选择排序
        bubleSort(arr);		//冒泡排序
        System.out.println("Sorted Array: " + toString(arr));
        
        //测试二分查找
        int[] test = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        System.out.println( halfSearch(test, 10) );
    }
}